import pandas as pd
from tabulate import tabulate

class LALRAnalyzer:
    def __init__(self):
        # 产生式规则
        self.productions = {
            1: ('program', ['statement_list']),
            2: ('statement_list', ['statement']),
            3: ('statement_list', ['statement_list', 'statement']),
            4: ('statement', ['declaration', 'SEMICOLON']),
            5: ('statement', ['assignment', 'SEMICOLON']),
            6: ('statement', ['expr', 'SEMICOLON']),
            7: ('statement', ['if_statement']),
            8: ('statement', ['while_statement']),
            9: ('declaration', ['INT', 'IDENTIFIER']),
            10: ('declaration', ['FLOAT', 'IDENTIFIER']),
            11: ('assignment', ['IDENTIFIER', 'ASSIGN', 'expr']),
            12: ('expr', ['expr', '+', 'term']),
            13: ('expr', ['expr', '-', 'term']),
            14: ('expr', ['expr', 'GT', 'term']),
            15: ('expr', ['term']),
            16: ('term', ['term', '*', 'factor']),
            17: ('term', ['term', '/', 'factor']),
            18: ('term', ['factor']),
            19: ('factor', ['NUMBER']),
            20: ('factor', ['IDENTIFIER']),
            21: ('factor', ['-', 'factor']),
            22: ('factor', ['LPAREN', 'expr', 'RPAREN']),
            23: ('while_statement', ['WHILE', 'LPAREN', 'expr', 'RPAREN', 'LBRACE', 'statement_list', 'RBRACE'])
        }

        # 初始化LALR分析表
        self.action_table = {
            0: {'INT': 's3', 'IDENTIFIER': 's2', 'NUMBER': 's1', 'WHILE': 's6', 'LPAREN': 's7', '-': 's8', '$': 'r1'},
            1: {'SEMICOLON': 'r19', '+': 'r19', '-': 'r19', '*': 'r19', '/': 'r19', 'GT': 'r19', 'RPAREN': 'r19'},
            2: {'ASSIGN': 's19', 'SEMICOLON': 'r20', '+': 'r20', '-': 'r20', '*': 'r20', '/': 'r20', 'GT': 'r20'},
            3: {'IDENTIFIER': 's20'},
            6: {'LPAREN': 's23'},
            7: {'NUMBER': 's1', 'IDENTIFIER': 's24', 'LPAREN': 's7', '-': 's8'},
            8: {'NUMBER': 's1', 'IDENTIFIER': 's24', 'LPAREN': 's7', '-': 's8'},
            10: {'INT': 's3', 'IDENTIFIER': 's2', 'WHILE': 's6', 'LPAREN': 's7', '-': 's8', '$': 'acc'},
            11: {'$': 'r2', 'INT': 'r2', 'IDENTIFIER': 'r2', 'WHILE': 'r2', 'RBRACE': 'r2'},
            12: {'SEMICOLON': 's29'},
            13: {'SEMICOLON': 's30'},
            14: {'SEMICOLON': 's31', '+': 's38', '-': 's39', 'GT': 's32'},
            15: {'SEMICOLON': 'r15', '+': 'r15', '-': 'r15', 'GT': 'r15', '*': 's40', '/': 's41', 'RPAREN': 'r15'},
            16: {'SEMICOLON': 'r18', '+': 'r18', '-': 'r18', '*': 'r18', '/': 'r18', 'GT': 'r18', 'RPAREN': 'r18'},
            18: {'$': 'r8', 'INT': 'r8', 'IDENTIFIER': 'r8', 'WHILE': 'r8', 'RBRACE': 'r8'},
            19: {'NUMBER': 's1', 'IDENTIFIER': 's24', 'LPAREN': 's7', '-': 's8'},
            20: {'SEMICOLON': 'r9'},
            23: {'NUMBER': 's1', 'IDENTIFIER': 's24', 'LPAREN': 's7', '-': 's8'},
            24: {'SEMICOLON': 'r20', '+': 'r20', '-': 'r20', '*': 'r20', '/': 'r20', 'GT': 'r20', 'RPAREN': 'r20'},
            25: {'RPAREN': 's45', '+': 's38', '-': 's39', 'GT': 's32'},
            26: {'SEMICOLON': 'r21', '+': 'r21', '-': 'r21', '*': 'r21', '/': 'r21', 'GT': 'r21', 'RPAREN': 'r21'},
            28: {'$': 'r3', 'INT': 'r3', 'IDENTIFIER': 'r3', 'WHILE': 'r3', 'RBRACE': 'r3'},
            29: {'$': 'r4', 'INT': 'r4', 'IDENTIFIER': 'r4', 'WHILE': 'r4', 'RBRACE': 'r4'},
            30: {'$': 'r5', 'INT': 'r5', 'IDENTIFIER': 'r5', 'WHILE': 'r5', 'RBRACE': 'r5'},
            31: {'$': 'r6', 'INT': 'r6', 'IDENTIFIER': 'r6', 'WHILE': 'r6', 'RBRACE': 'r6'},
            32: {'NUMBER': 's1', 'IDENTIFIER': 's24', 'LPAREN': 's7', '-': 's8', 'RPAREN': 'r14'},
            38: {'NUMBER': 's1', 'IDENTIFIER': 's24', 'LPAREN': 's7', '-': 's8'},
            39: {'NUMBER': 's1', 'IDENTIFIER': 's24', 'LPAREN': 's7', '-': 's8'},
            40: {'NUMBER': 's1', 'IDENTIFIER': 's24', 'LPAREN': 's7', '-': 's8'},
            41: {'NUMBER': 's1', 'IDENTIFIER': 's24', 'LPAREN': 's7', '-': 's8'},
            42: {'SEMICOLON': 'r11', '+': 's38', '-': 's39', 'GT': 's32'},
            44: {'RPAREN': 's57', '+': 's38', '-': 's39', 'GT': 's32'},
            45: {'LBRACE': 's58'},
            46: {'SEMICOLON': 'r14', '+': 'r14', '-': 'r14', '*': 's40', '/': 's41', 'RPAREN': 'r14'},
            52: {'SEMICOLON': 'r12', '+': 'r12', '-': 'r12', '*': 's40', '/': 's41', 'RPAREN': 'r12'},
            53: {'SEMICOLON': 'r13', '+': 'r13', '-': 'r13', '*': 's40', '/': 's41', 'RPAREN': 'r13'},
            54: {'SEMICOLON': 'r16', '+': 'r16', '-': 'r16', '*': 'r16', '/': 'r16', 'GT': 'r16', 'RPAREN': 'r16'},
            55: {'SEMICOLON': 'r17', '+': 'r17', '-': 'r17', '*': 'r17', '/': 'r17', 'GT': 'r17', 'RPAREN': 'r17'},
            57: {'LBRACE': 's59'},
            58: {'INT': 's3', 'IDENTIFIER': 's2', 'NUMBER': 's1', 'WHILE': 's6', 'LPAREN': 's7', '-': 's8'},
            59: {'INT': 's3', 'IDENTIFIER': 's2', 'NUMBER': 's1', 'WHILE': 's6', 'LPAREN': 's7', '-': 's8'},
            60: {'RBRACE': 's62', 'INT': 's3', 'IDENTIFIER': 's2', 'NUMBER': 's1', 'WHILE': 's6', 'LPAREN': 's7', '-': 's8'},
            61: {'RBRACE': 's63', 'INT': 's3', 'IDENTIFIER': 's2', 'NUMBER': 's1', 'WHILE': 's6', 'LPAREN': 's7', '-': 's8'},
            62: {'$': 'r28', 'INT': 'r28', 'IDENTIFIER': 'r28', 'WHILE': 'r28', 'RBRACE': 'r28'},
            63: {'$': 'r23', 'INT': 'r23', 'IDENTIFIER': 'r23', 'WHILE': 'r23', 'RBRACE': 'r23'}
        }
        
        self.goto_table = {
            0: {'program': 9, 'statement_list': 10, 'statement': 11, 'declaration': 12, 'assignment': 13,
                'expr': 14, 'term': 15, 'factor': 16, 'while_statement': 18},
            7: {'expr': 25, 'term': 15, 'factor': 16},
            8: {'factor': 26},
            10: {'statement': 28, 'declaration': 12, 'assignment': 13, 'expr': 14, 'term': 15, 'factor': 16, 'while_statement': 18},
            19: {'expr': 42, 'term': 15, 'factor': 16},
            23: {'expr': 44, 'term': 15, 'factor': 16},
            32: {'term': 46, 'factor': 16},
            38: {'term': 52, 'factor': 16},
            39: {'term': 53, 'factor': 16},
            40: {'factor': 54},
            41: {'factor': 55},
            58: {'statement_list': 60, 'statement': 11, 'declaration': 12, 'assignment': 13,
                 'expr': 14, 'term': 15, 'factor': 16, 'while_statement': 18},
            59: {'statement_list': 61, 'statement': 11, 'declaration': 12, 'assignment': 13,
                 'expr': 14, 'term': 15, 'factor': 16, 'while_statement': 18},
            60: {'statement': 28},
            61: {'statement': 28}
        }

    def analyze(self, input_tokens):
        state_stack = [0]    # 状态栈
        symbol_stack = ['$'] # 符号栈
        input_queue = input_tokens + ['$']  # 输入串
        steps = []           # 存储每一步的分析过程
        
        step_num = 1
        while True:
            current_state = state_stack[-1]
            current_input = input_queue[0]
            
            print(f"\nStep {step_num}:")
            print(f"Current State: {current_state}")
            print(f"Current Input: {current_input}")
            print(f"State Stack: {state_stack}")
            print(f"Symbol Stack: {symbol_stack}")
            print(f"Input Queue: {input_queue[:3]}...")
            
            # 获取动作
            if current_input in self.action_table[current_state]:
                action = self.action_table[current_state][current_input]
                print(f"Action: {action}")
            else:
                action = 'error'
                print(f"Error: No action found for state {current_state} and input {current_input}")
                print(f"Available actions for state {current_state}: {self.action_table[current_state]}")
            
            # 记录当前步骤
            step = {
                'Step': step_num,
                'State Stack': str(state_stack),
                'Symbol Stack': str(symbol_stack),
                'Input': str(input_queue[:3]) + "...",
                'Action': action,
                'Goto': '-'
            }
            
            # 根据动作类型执行相应操作
            if action.startswith('s'):  # shift
                next_state = int(action[1:])
                state_stack.append(next_state)
                symbol_stack.append(current_input)
                input_queue.pop(0)
                step['Action'] = f'shift {next_state}'
                print(f"Shift to state {next_state}")
                
            elif action.startswith('r'):  # reduce
                rule_num = int(action[1:])
                production = self.productions[rule_num]
                rhs_length = len(production[1])
                
                print(f"Reduce using rule {rule_num}: {production[0]} -> {' '.join(production[1])}")
                
                # 弹出右部符号对应的状态和符号
                for _ in range(rhs_length):
                    state_stack.pop()
                    symbol_stack.pop()
                
                # 获取当前状态
                current_state = state_stack[-1]
                # 压入左部非终结符
                symbol_stack.append(production[0])
                
                # 查找GOTO表
                if production[0] in self.goto_table[current_state]:
                    next_state = self.goto_table[current_state][production[0]]
                    state_stack.append(next_state)
                    step['Goto'] = f'goto {next_state}'
                    print(f"Goto state {next_state}")
                else:
                    print(f"Error: No goto action found for state {current_state} and symbol {production[0]}")
                    print(f"Available goto actions for state {current_state}: {self.goto_table.get(current_state, {})}")
                
                step['Action'] = f'reduce {production[0]} -> {" ".join(production[1])}'
                
            elif action == 'acc':  # accept
                step['Action'] = 'accept'
                steps.append(step)
                print("Input accepted!")
                break
                
            elif action == 'error':
                step['Action'] = 'error'
                steps.append(step)
                raise Exception(f'Syntax error at step {step_num}, state {current_state}, input {current_input}')
            
            steps.append(step)
            step_num += 1
            
        return steps

    def print_analysis_table(self, steps):
        # 使用pandas创建表格
        df = pd.DataFrame(steps)
        print("\nLALR Analysis Steps:")
        print(tabulate(df, headers='keys', tablefmt='grid', showindex=False))

def main():
    # 测试用例：分析 "int x; x = 5; while (x > 0) { x = x - 1; }"
    input_tokens = [
        'INT', 'IDENTIFIER', 'SEMICOLON',
        'IDENTIFIER', 'ASSIGN', 'NUMBER', 'SEMICOLON',
        'WHILE', 'LPAREN', 'IDENTIFIER', 'GT', 'NUMBER', 'RPAREN',
        'LBRACE', 'IDENTIFIER', 'ASSIGN', 'IDENTIFIER', '-', 'NUMBER', 'SEMICOLON', 'RBRACE'
    ]
    
    print("Input tokens:", input_tokens)
    
    analyzer = LALRAnalyzer()
    try:
        steps = analyzer.analyze(input_tokens)
        analyzer.print_analysis_table(steps)
    except Exception as e:
        print(f"\nError: {e}")

if __name__ == "__main__":
    main() 